The invention relates generally to a method for communication of digital data packets. More particularly, this invention relates to a technique for minimizing contention due to simultaneous transmissions via radio communication links between nodes in a packet communication network.
Packet communication networks provide for the transfer of data packets between various remote locations herein referred to as nodes. Nodes are equipped with transmitters and receivers that can transmit data over a medium, which may be radio waves, fiber optic cable, wire, etc. In a shared-medium network, more than one node is connected to the same medium, introducing the possibility of contention if more than one transmitter attempts to transmit on the medium at the same time. When there is contention, data packets clash, resulting in loss of data.
In order to avoid contention and for successful data transfer, each node must operate in accordance with a protocol determining when it may transfer on the medium, for how long, and, in a multiple frequency network, at what frequency. Additional protocol tasks include error checking and error correction.
In a polled network, the protocol is implemented by having a transmitter that wishes to transmit a data packet first send a short poll packet to the receiver asking if the receiver is available to receive the data packet. If the transmitter receives an acknowledgement back from the intended receiver, the data packet is then sent. In a type of network protocol known as a time-slotted network protocol, there is a designated window of time, known to all nodes, when poll packets may be transmitted. When a poll packet is successfully transmitted and acknowledged during this designated period of time, data may then be transmitted during a subsequent window of time, a data window. While this procedure effectively ensures that the receiver will be free to receive the data being sent, it does not necessarily prevent other transmitters on the network from transmitting on the medium during the data packet transmission and thereby causing contention.
Several specific protocols have been employed for resolving this latter type of contention. Among them is the Carrier Sense Multiple Access/Collision Detect or CSMA/CD protocol, wherein the transmitter in each node is responsible for detecting and avoiding data packet collisions. Transmitters listen to the medium before transmitting (the Carrier Sense) and then listen while transmitting to see if a collision has occurred (the Collision Detect). This protocol is most useful where it is practical to detect collisions while a packet is being transmitted. It is less useful in communications systems where the medium is radio waves because it is expensive to implement a transmitter that can listen for collisions while transmitting.
Other protocols that are more useful for radio links are the Aloha protocol and the slotted Aloha protocol. In these protocols, the transmitter nodes respond to the failure to receive an acknowledgement of reception transmitted by the destination node. In the Aloha protocol, the transmitter nodes know merely to try again later in the event of a failure to receive an acknowledgement, while in the slotted Aloha protocol, the transmitter nodes are commanded by the destination node to transmit on a schedule determined by the destination node.
The disadvantage of these protocols is primarily that they become more complex as the number of potential transmitter nodes on the medium increases and a large amount of the available time on the medium becomes diverted away from sending data and is instead involved in transmitting poll information. This reduces the overall data throughput of the network. The protocols are particularly inefficient when applied to a peer-to-peer network where there is no network controller that can determine when a channel has been reserved by a particular transmitter and prevent other transmitters from transmitting during that time and causing contention.
U.S. Pat. No. 5,079,768, issued to one of the inventors of the present invention, describes a peer-to-peer frequency-hopping communication network in which every receiver node is assigned a different starting point or home slot in a frequency hopping pattern. The frequency-hopping pattern is a randomized ordered list of all the channels available to nodes in the network. The channel order is shared by all the nodes in the network, but contention is reduced by having each node start its channel hopping at a different channel in the list. Transmitters wishing to transmit to a receiver node switch to that receiver's current frequency in the hopping pattern to transmit a poll packet. The transmitter first listens at the assigned frequency of the receiver to determine if there is any traffic on that frequency. If there is traffic at that frequency, the transmitter waits an interval and the transmitter and receiver both hop to the next frequency in the pattern and the transmitter listens again. Once a frequency is found with no traffic, the transmitter sends a poll packet, and when that poll packet is acknowledged, sends a data packet before the hop to the next frequency. In a particular embodiment of this network, frequency hopping occurs once every second. It has been found that there can be a relatively large amount of wasted potential data transmission time with this design while transmitters and receivers look for an empty frequency. Effective throughput is limited to a fraction of potential throughput.
What is needed is a low-cost, reliable mechanism for reserving only the network resources required for the time period required, and which is simple to implement and yet has very low overhead.